/*
 * @lc app=leetcode id=479 lang=cpp
 *
 * [479] Largest Palindrome Product
 */

// @lc code=start
class Solution {
public:
    int largestPalindrome(int n) {
        if (n == 1) {
		return 9;
        }
        int64_t low, high;
        int64_t num;
        int64_t pal;
        int64_t i;
        low = (int64_t)pow(10, n - 1);
        high = (int64_t)pow(10, n) - 1;
        for (num = high; num >= low; --num) {
            pal = GetPalindrome(num);
            for (i = high; pal / i <= high && i >= low; --i) {
                if (pal % i == 0) {
                    return pal % 1337;
                }
            }
        }
        return 0;
    }
    int64_t GetPalindrome(int n) {
        if (n < 0) {
            return 0;
        }
        int64_t n0 = n;
        int64_t n1 = 0;
        while (n > 0) {
            n1 = n1 * 10 + (n % 10);
            n0 *= 10;
            n /= 10;
        }
        return n1 + n0;

    }
};
// @lc code=end

